#include <stdio.h>
#include <stdlib.h>


typedef struct {
	char name[20];
	float score;
} Student;

struct Node {
	Student *student;
	struct Node *next;
	struct Node *prev;
};

typedef struct {
	struct Node *head;
	struct Node *tail;
	int size;
} LinkedList;

LinkedList linkedList;

int studentSize() { return linkedList.size; }

struct Node *node(int index) {
	// 索引范围检测
	if (index < 0 || index >= linkedList.size) {
		return NULL;
	}

	// 优化链表的查找
	if (index < (linkedList.size >> 1)) {
		// 从链表的头部向下查找
		struct Node *node = linkedList.head;
		for (int i = 0; i < index; i++) {
			node = node->next;
		}
		return node;
	}
	else {
		// 从链表的尾部向上查找
		struct Node *node = linkedList.tail;
		for (int i = linkedList.size - 1; i > index; i--) {
			node = node->prev;
		}
		return node;
	}
}


Student *getStudent(int index) {
	struct Node *currentNode = node(index);
	if (currentNode == NULL) {
		return NULL;
	}
	return currentNode->student;
}

void add(Student *student) {
	// 动态分配内存，防止函数结束，变量内存回收
	struct Node *node = (struct Node *) malloc(sizeof(struct Node));
	node->student = student;
	node->next = NULL;
	node->prev = NULL;

	if (linkedList.head == NULL) {
		linkedList.head = node;
		linkedList.tail = node;
	}
	else {
		// 节点关联
		linkedList.tail->next = node;
		node->prev = linkedList.tail;
		linkedList.tail = node;
	}

	linkedList.size++;
}

void removeStudent(int index) {
	struct Node *currentNode = node(index);
	if (currentNode == NULL) {
		return;
	}
	struct Node *prevNode = currentNode->prev;
	struct Node *nextNode = currentNode->next;

	// 上一个节点操作
	if (prevNode == NULL) {
		linkedList.head = nextNode;
	}
	else {
		// 修改前驱节点
		prevNode->next = nextNode;
		currentNode->prev = NULL;
	}

	if (nextNode == NULL) {
		linkedList.tail = prevNode;
	}
	else {
		// 修改后继节点
		nextNode->prev = prevNode;
		currentNode->next = NULL;
	}

	// 将指针置为 NULL，防止成为悬空指针
	currentNode->student = NULL;

	// 释放此节点的内存
	free(currentNode);


	linkedList.size--;
}

void print() {
	struct Node *currentNode = linkedList.head;
	for (int i = 0; i < linkedList.size; i++) {
		printf("%s %f\n", currentNode->student->name, currentNode->student->score);
		currentNode = currentNode->next;
	}
}

void quick_sort(struct Node *array[], int left, int right) {
	// 递归退出条件
	if (left < right) {
		// 基准值
		struct Node *pivot = array[right];
		int i = left - 1, j = right;
		// 基于基准值，将数组分治排序
		while (1) {
			// 左侧大于等于基准值的索引
			while (array[++i]->student->score < pivot->student->score);
			// 右侧小于等于基准值的索引
			while (array[--j]->student->score > pivot->student->score);
			// 两侧索引位置没有相交，则交换
			if (i >= j) break;
			struct Node *temp = array[i];
			array[i] = array[j];
			array[j] = temp;
		}

		// 将基准值放到正确的位置
		array[right] = array[i];
		array[i] = pivot;

		// 左侧递归
		quick_sort(array, left, i - 1);
		// 右侧递归
		quick_sort(array, i + 1, right);
	}
}

void sort() {
	// 链表转为数组进行排序
	struct Node *array[linkedList.size];
	struct Node *currentNode = linkedList.head;
	for (int i = 0; i < linkedList.size; i++) {
		array[i] = currentNode;
		currentNode = currentNode->next;
	}

	quick_sort(array, 0, linkedList.size - 1);


	// 重新连接链表
	linkedList.head = array[0];
	linkedList.head->prev = NULL;
	linkedList.head->next = array[1];
	linkedList.tail = array[linkedList.size - 1];
	linkedList.tail->prev = array[linkedList.size - 2];
	linkedList.tail->next = NULL;

	for (int i = 1; i < linkedList.size - 1; i++) {
		struct Node *node = array[i];
		node->prev = array[i - 1];
		node->next = array[i + 1];
	}
}

void avg() {
	float sum = 0;
	struct Node *currentNode = linkedList.head;
	for (int i = 0; i < linkedList.size; i++) {
		sum += currentNode->student->score;
		currentNode = currentNode->next;
	}
	// 求和除以数量
	printf("AVG = %f\n", sum / linkedList.size);
}

void median() {
	// 计算数量奇偶数
	int odd = linkedList.size & 0B0001;
	if (odd) {
		// 奇数取中间值
		int index = linkedList.size / 2;
		printf("MEDIAN = %f\n", getStudent(index)->score);
	}
	else {
		// 偶数取两个中间数的平均值
		int index1 = linkedList.size / 2 - 1;
		int index2 = index1 + 1;
		float sum = getStudent(index1)->score + getStudent(index2)->score;
		printf("MEDIAN = %f\n", sum / 2);
	}
}


int main() {

	printf("size = %i\n", studentSize());

	Student student1 = {.name = "John", .score = 90.0F};
	Student student2 = {.name = "Mary", .score = 80.0F};
	Student student3 = {.name = "Peter", .score = 30.0F};
	Student student4 = {.name = "Paul", .score = 60.0F};
	Student student5 = {.name = "George", .score = 50.0F};
	Student student6 = {.name = "Ringo", .score = 70.0F};
	Student student7 = {.name = "Tom", .score = 100.0F};
	Student student8 = {.name = "Jack", .score = 80.0F};
	Student student9 = {.name = "Jerry", .score = 20.0F};
	Student student10 = {.name = "Mike", .score = 85.0F};



	// 添加操作
	printf("\n---------------- Add operate ----------------\n");
	add(&student1);
	add(&student2);
	add(&student3);
	add(&student4);
	add(&student5);
	add(&student6);
	add(&student7);
	add(&student8);
	add(&student9);
	add(&student10);

	printf("size = %i\n", studentSize());
	print();

	// 排序操作
	printf("\n---------------- Sort operate ----------------\n");
	sort();
	print();

	// 平均值操作
	printf("\n---------------- Avg operate ----------------\n");
	avg();

	// 中位数操作
	printf("\n---------------- Median operate ----------------\n");
	median();

	// 最高分
	printf("\n---------------- Highest operate ----------------\n");
	printf("HIGHEST = %f\n", linkedList.tail->student->score);

	// 最低分
	printf("\n---------------- Lowest operate ----------------\n");
	printf("LOWEST = %f\n", linkedList.head->student->score);

	// 查询操作
	printf("\n---------------- Find operate ----------------\n");
	Student *student = getStudent(0);
	printf("%s %f\n", student->name, student->score);

	// 修改操作
	printf("\n---------------- Modify operate ----------------\n");
	student->score = 80.0F;
	student = getStudent(0);
	printf("%s %f\n", student->name, student->score);

	// 删除操作
	printf("\n---------------- Remove operate ----------------\n");
	removeStudent(0);
	student = getStudent(0);
	printf("%s %f\n", student->name, student->score);

}

